\documentclass[revision]{FPSAC2017}

\articlenumber{36}
\addbibresource{36_Nadeau_Muhle.bib}

%% PACKAGES
\usepackage{lipsum}
\usepackage{tikz}
%%
\makeatletter
%% Allows to reference description items correctly
\let\orgdescriptionlabel\descriptionlabel
\renewcommand*{\descriptionlabel}[1]{%
  \let\orglabel\label
  \let\label\@gobble
  \phantomsection
  \edef\@currentlabel{#1}%
  %\edef\@currentlabelname{#1}%
  \let\label\orglabel
  \orgdescriptionlabel{(#1)}%
}
\makeatother

%% THEOREMS
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

%% COMMANDS
\newcommand{\henri}[1]{\todo[size=\tiny,color=orange!30]{#1 \\ \hfill --- H.}}
\newcommand{\filip}[1]{\todo[size=\tiny,color=green!30]{#1 \\ \hfill --- Ph.}}
\newcommand{\defn}[1]{\emph{#1}}
\renewcommand{\AA}{\mathfrak{A}}
\newcommand{\AAo}{\mathfrak{A}^{o}}
\newcommand{\BB}{\mathfrak{B}}
\newcommand{\PP}{\mathcal{P}}
\renewcommand{\SS}{\mathfrak{S}}
\newcommand{\gen}{\mathcal{T}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\ocyc}{\text{ocyc}}
\newcommand{\nc}{N\!C}
\newcommand{\pnc}{\mathcal{N\!C}}
\newcommand{\enc}{E\!N\!C}
\newcommand{\penc}{\mathcal{E\!N\!C}}
\newcommand{\red}{\text{Red}}
\newcommand{\supp}{\text{supp}}
\newcommand{\ran}{\text{Ran}}
\newcommand{\rk}{\text{rk}}

\title{The Alternating Group Generated by $3$-Cycles}

\author{Henri M{\"u}hle\thanks{H.M. was partially supported by Digiteo project PAAGT (Nr. 2015-3161D).}\addressmark{1} \and Philippe Nadeau\addressmark{2}}

\address{\addressmark{1}Institut f{\"u}r Algebra, Technische Universit{\"a}t Dresden.\\ \addressmark{2}Universit\'e de Lyon, CNRS, ICJ UMR 5208, , F-69622 Villeurbanne cedex, France}

\received{\today}

\abstract{We investigate the partial order on the alternating group generated by all $3$-cycles. We  first describe the cover relations in this poset.  Permutations with odd cycles occur naturally, and we study the lower intervals they induce. These intervals are naturally embedded in the lattices of noncrossing partitions, and we provide several enumeration formulas for them.   We also study the natural action of the braid group on the maximal chains in any given interval, and determine when this action is transitive.  We also outline the many ways in which our construction can, or could, be extended.}

\resume{Nous \'etudions l'ordre partiel sur le groupe altern\'e engendr\'e par les $3$-cycles. Nous d\'ecrivons d'abord les relations de couvertures de ce poset. Les permutations avec cycles impairs apparaissent naturellement, et nous \'etudions les intervalles inf\'erieurs qu'elles induisent. Ces intervalles sont naturellement plong\'es dans les treillis de partitions non crois\'ees, et nous donnons de nombreuses formules \'enum\'eratives. Nous \'etudions de plus l'action du groupe de tresses sur les cha\^ines maximales de tout intervalle de notre poset et d\'eterminons quand celle-ci est transitive. Nous esquissons aussi les mani\`eres possibles ou envisageables d'\'etendre notre contruction.}

\keywords{noncrossing partition, cycle, permutation factorization, poset, braid group, Hurwitz action, Coxeter group}


\begin{document}

\maketitle

\section{Introduction}
	\label{sec:introduction}

Given a group $G$ generated by a finite set $\gen$ closed under taking inverses, the (right) Cayley graph $C(G,\gen)$ is one of the most fundamental geometric objects to attach to it. Recall that the vertex set of $C(G,\gen)$ is $G$, and that its edges are of the form $(g,gt)$ for $g\in G,t\in\gen$. Since $\gen=\gen^{-1}$  the graph $C(G,\gen)$ is considered undirected, and comes with a natural graph distance which can be written as $d_C(g,g')=\ell_{\gen}(g^{-1}g')$. Here the \defn{length} $\ell_{\gen}(g)$ is the minimum $k$ such that there exists a factorization $g=t_1t_2\cdots t_k$ where each $t_i$ is in $\gen$. Such factorizations are \defn{$\gen$-reduced} and $\red_{\gen}(g)$ denotes the set of all $\gen$-reduced factorizations of $g$.

The relation defined by $u\leq_{\gen}v$ if and only if $\ell_{\gen}(v)=\ell_{\gen}(u)+\ell_{\gen}(u^{-1}v)$ is a partial order on $G$, graded by $\ell_\gen$. Geometrically, $u\leq_{\gen}v$ if $u$ occurs on a geodesic from the identity $e$ to $v$ in $C(G,\gen)$.
\medskip

The goal of this work is to study this poset when $G=\AA_{N}$ is the alternating group and $\gen$ is the set of all $3$-cycles. In that case we replace the subscript ``$\gen$'' by a ``$3$'' in all of the above definitions.\smallskip

The motivating example is the case where $G=\SS_{N}$ is the symmetric group and $\gen$ is the set of all transpositions.  We will often compare how our results are related to this case, and we use the subscript ``$2$'' to refer to this example.  It is a standard fact that $\ell_2(x)=n-\text{cyc}(x)$, where $\text{cyc}(x)$ denotes the number of cycles of $x$. The poset $(\SS_{N},\leq_2)$ was for instance studied in \cite{athanasiadis08absolute}.  Moreover, it was observed in \cite{biane97some} that the \defn{lattice of noncrossing partitions} arises as the principal order ideal $\pnc_{N}=[e,c]_{2}$ where $c$ is the $N$-cycle $c=(1\;2\;\ldots\;N)$.  See \cite{simion00noncrossing} for a survey on these lattices, and \cite{kreweras72sur} for some enumerative and structural properties:
\medskip

We come back to the case of a general pair $(G,\gen)$. 
\smallskip

 \emph{We assume from now on that $\gen$ is closed under $G$-conjugation}.
With this extra assumption, the following pleasant properties hold (and are easily proved, see~\cite[Section~2]{huang15absolute}).\smallskip

$\bullet$ If $x,x'\in G$ are $G$-conjugate, then $\ell_{\gen}(x)=\ell_{\gen}(x')$, and more generally the intervals $[e,x]_{\gen}$ and $[e,x']_{\gen}$ are isomorphic.  In fact, even when $\gen\subseteq G$ is closed under $G$-conjugation, but generates a strict subgroup $H$, this isomorphism remains true for any $x,x'\in H$ that are $G$-conjugate  (and not necessarily $H$-conjugate).\smallskip

$\bullet$ For any $y\leq_{\gen}z$ the bijection $G\to G$ defined by $x\mapsto yx^{-1}z$ restricts to a poset anti-isomorphism $[y,z]_{\gen}\to[y,z]_{\gen}$ (so the order is always locally self-dual).  One particular instance of such a bijection is the \defn{Kreweras complement} $K_{z}(x)=x^{-1}z$.  The map $K_{z}\circ K_{y^{-1}z}$ is therefore an isomorphism from $[y,z]_{\gen}$ to $[e,y^{-1}z]_{\gen}$. \smallskip

$\bullet$ For any $k\geq 2$, the set $\gen^k$ of words over $\gen$ of  length $k$ affords an action of the braid group $\BB_{k}$ on $k$ strands, the \defn{Hurwitz action}.  Recall that $\BB_{k}$ has generators $\sigma_{1},\sigma_{2},\ldots,\sigma_{k-1}$ and relations $\sigma_{i}\sigma_{i+1}\sigma_{i}=\sigma_{i+1}\sigma_{i}\sigma_{i+1}$ and $\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ for $\lvert j-i\rvert>1$.  

If $\xx=t_{1}t_{2}\cdots t_{k}$ is a word over $\gen$, then the \defn{Hurwitz operator} $\sigma_{i}$ acts on $\xx$ by
\begin{align*}
	\sigma_{i}\cdot\xx & = t_{1}t_{2}\cdots t_{i-1}t_{i+1}(t_{i+1}^{-1}t_{i}t_{i+1})t_{i+2}\cdots t_{k},
\end{align*}
and its inverse $\sigma_{i}^{-1}$ reverts this process. Two words are \defn{Hurwitz-equivalent} if they are in the same orbit for this action.  It is clear that two Hurwitz-equivalent words represent the same element in $G$. In particular, $\red_{\gen}(x)$ affords an action of $\BB_{\ell_{T}(x)}$ for any $x\in G$.
\medskip

For $N\geq 3$, the set of all $3$-cycles is closed under $\SS_{N}$-conjugation.  (In fact, for $N\geq 5$, it is even closed under $\AA_{N}$-conjugation.)  The poset $(\AA_{N},\leq_{3})$ therefore has all the properties described above.  It turns out that the subposet determined by the set $\AAo_{N}$ of permutations with only odd cycles plays a special role.  For instance, its intervals can be embedded into  $(\SS_{N},\leq_2)$ as our first main result shows.  

\begin{theorem}\label{thm:induced_subposet}
	For $N\geq 3$ and $x\in\AAo_{N}$ the interval $[e,x]_{3}$ is an induced subposet of the interval $[e,x]_{2}$ in $(\SS_{N},\leq_{2})$.
\end{theorem}

We will moreover prove that any lower interval in $(\AAo_{N},\leq_3)$ can be written as a direct product of intervals induced by a single odd cycle (\cref{prop:interval_decomposition}).  Since the set of $3$-cycles is invariant under conjugation, the structure of any interval in $(\AAo_{N},\leq_3)$ can be deduced from the structure of the posets $\penc_{2n+1}:=[e,(1\;2\;\ldots\;2n\!+\!1)]_{3}$.  

Our second main result determines the decomposition numbers of this poset.  (See \cref{sec:enumeration} for any undefined terminology.)

\begin{theorem}\label{thm:enc_multichains}
	For $n,m\geq 1$, the number of $(m-1)$-multichains of $\penc_{2n+1}$ with rank-jump vector $(r_{1},r_{2},\ldots,r_{m})$ is 
	\begin{displaymath}
		(2n+1)^{m-1}\prod_{i=1}^{m}{\frac{1}{2n-2r_{i}+1}\binom{2n-r_{i}}{r_{i}}}.
	\end{displaymath}
\end{theorem}

Finally, our third main result further emphasizes the special role of $\AAo_{N}$: it consists of all elements whose induced order ideals afford a transitive Hurwitz action. 

\begin{theorem}\label{thm:hurwitz_transitivity}
	For $N\geq 3$ we have $x\in\AAo_{N}$ if and only if $\BB_{\ell_{3}(x)}$ acts transitively on $\red_{3}(x)$.
\end{theorem}

The rest of this abstract is organized as follows: in \cref{sec:covers} we give an explicit formula for the length function $\ell_{3}$ together with a characterization of the cover relations in $(\AA_{N},\leq_{3})$.  In \cref{sec:embedding} we prove \cref{thm:induced_subposet} and introduce the posets $\penc_{2n+1}$.  In \cref{sec:enumeration}, we prove \cref{thm:enc_multichains} and provide further enumerative results.  In \cref{sec:hurwitz} we determine the number of orbits under the Hurwitz action for the reduced factorizations of any element in $\AA_{N}$, and thus obtain the proof of \cref{thm:hurwitz_transitivity}.  We finish this abstract with an outlook on possible extensions and generalizations of this construction in \cref{sec:extensions}.


%%%%%%%%%%%%%%%%	
\section{A New Order on Alternating Groups}
	\label{sec:absolute_alternating}
%%%%%%%%%%%%%%%%	
\subsection{Structural Properties}
	\label{sec:covers}
To analyze the graded poset $(\AA_{N},\leq_{3})$, the starting point is naturally to give an explicit formula for the length function $\ell_3$. For $x\in\AA_{N}$ let $\ocyc(x)$ denote the number of cycles of $x$ with odd length. The following result seems to have been established only in  \cite[Corollary~2.4~(i)]{herzog76representation}, so we will sketch an independent proof.\medskip

\begin{proposition}\label{prop:alternating_length}
	For $N\geq 3$ and $x\in\AA_{N}$ , we have $\ell_{3}(x)=\tfrac{N-\ocyc(x)}{2}$.
\end{proposition}

\begin{proof}[Sketch of the proof]
	Given $x\in \AA_{N}$ and a $3$-cycle $a$, it is easily checked that there are three cases for the relation between the cycle decompositions of $x$ and $xa$:  three cycles of $x$ are merged into one,   one cycle is cut into three, and two cycles are merged and the result then cut in two. 

Now let $r(x):=\tfrac{N-\ocyc(x)}{2}$. Notice that $r(e)=0$, and by the analysis above there holds $r(xa)\leq r(x)+1$ in any case. Therefore $r(x)\leq \ell_3(x)$ for any $x$. On the other hand, for any $x\neq e$, one can construct a $3$-cycle $a$ such that $r(xa)=r(x)-1$. 
This is enough to show that $r=\ell_3$.
\end{proof}

 Recall that in a poset $(P,\leq)$ a \defn{cover relation} is a pair $(x,y)$ such that $x<y$ and there is no $z\in P$ with $x<z<y$; we then write $x\lessdot y$. From the previous proposition and its proof we obtain the following description of $\leq_3$:

\begin{proposition}\label{prop:alternating_covers}
	Let $y\in\AA_{N}$.  An element $x$ satisfies $x\lessdot_3 y$ if and only if it is obtained by one of the following operations:
	\begin{enumerate}
		\item\label{cover_odd} Pick an odd cycle of $y$ and split it into three odd cycles.
		\item\label{cover_even_1} Pick an even cycle of $y$ and split it into two odd cycles and one even cycle.
		\item\label{cover_even_2} Pick two even cycles of $y$, join them, and split the resulting cycle into two odd cycles.
	\end{enumerate}
\end{proposition}


The next result describes a decomposition of the lower intervals in $(\AA_{N},\leq_{A})$.

\begin{proposition}\label{prop:interval_decomposition}
	Let $y\in\AA_{N}$. Write $y=\zeta_1\zeta_2\cdots \zeta_k\xi$ where the $\zeta_{i}$ are the odd cycles of $y$ and $\xi$ is the product of its even cycles.  Then we have a poset isomorphism
	\begin{displaymath}
		[e,y]_{3}\cong [e,\zeta_{1}]_{3}\times[e,\zeta_{2}]_{3}\times\cdots\times[e,\zeta_{k}]_{3}\times[e,\xi]_{3}.
	\end{displaymath}
	given by $f^{-1}$ where $f(x_{1},x_{2},\ldots,x_{k},y)=x_{1}x_{2}\cdots x_{k}y$.
\end{proposition}

\subsection{Embedding}
	\label{sec:embedding}
Let $\AAo_{N}\subseteq\AA_{N}$ be the subset of permutations having only odd cycles. In this case,  \cref{prop:alternating_length,prop:alternating_covers} become simpler.

\begin{proposition}\label{prop:odd_alternating}
	$\AAo_{N}$ is a lower ideal of $(\AA_{N},\leq_{3})$, and $\ell_{3}(x)=\tfrac{\ell_{2}(x)}{2}$ for $x\in\AAo_{N}$.  Moreover $x\lessdot y$ in $(\AAo_{N},\leq_{3})$ if and only if $x$ is obtained  by splitting an odd cycle of $y$ in three odd cycles. 
\end{proposition}

It follows, thanks to \cref{prop:interval_decomposition} and the invariance properties of  $\leq_3$, that any interval in $(\AAo_{N},\leq_{3})$ is isomorphic to a product of lower intervals induced by odd cycles. We proceed to describe the elements of such intervals.
\smallskip

Given an increasing cycle $(u_{1}<u_{2}<\cdots<u_{q})$ of a permutation, we define the following property:
\begin{description}
	\item[OD\label{it:od}] $q$ is odd and $u_{j+1}-u_{j}$ is odd for all $1\leq j \leq q-1$.
\end{description}

Recall from the introduction that $\nc_N$ is the set of elements in the interval $[e,x]_{2}$ for $x=(1\;2\;\ldots\;N)$. Permutations in $\nc_N$ are characterized by two properties (\cite{biane97some}): all of their cycles increasing, and they induce a noncrossing partition. We will say that $x\in\nc_{N}$ satisfies Property~\eqref{it:od} if all its cycles do.  It is  clear that  such permutations are in $\AAo_{N}$.

\begin{definition}\label{def:even_noncrossings}
	Let $N\geq 3$.  We define $\enc_{N}\subseteq \AAo_{N}$ to be the set of all elements $x\in\nc_{N}$ which satisfy Property~\eqref{it:od}.
\end{definition}

\begin{theorem}\label{thm:enc_interval}
	Let $n\geq 1$ and $x\in\AA_{2n+1}$. Then  $x\leq_{3}(1\;2\;\cdots\;2n\!+\!1)$ if and only if $x\in\enc_{2n+1}$.
\end{theorem}
\begin{proof}[Sketch of the proof]
	We write $c=(1\;2\;\cdots\;2n\!+\!1)$. In both directions we perform an induction on $n-\ell_{3}(x)$. The base of the induction is $x=c$ each time, which is clearly satisfied.

	To prove necessity, we can take $x<_{3}c$, and may thus find an upper cover $y\leq_{3}c$ of $x$ which by induction satisfies Property~\eqref{it:od}. \cref{prop:alternating_covers} implies that $x$ is constructed by splitting an odd cycle of $y$ into three odd cycles, and a case-distinction yields the claim that $x$ satisfies Property~\eqref{it:od}.
	
	To prove sufficiency, we take $x<_{2}c$ that satisfies Property~\eqref{it:od}, and denote by $\zeta_{1}$ the cycle of $x$ containing $1$.  Since $x\neq c$, there must be consecutive elements in $\zeta_{1}$ whose values differ by more than $1$.  Since $x\in\nc_{2n+1}$, there must be a cycle $\zeta_{2}$ in between these values, and since $x$ satisfies Property~\eqref{it:od} we can in fact find a third cycle $\zeta_{3}$ which also lies between these consecutive values.  Let $i,j,k$ denote the smallest elements of $\zeta_{1},\zeta_{2},\zeta_{3}$, respectively.  It is quickly verified that $y=x\cdot(i\;j\;k)$ is in $\nc_{2n+1}$ and satisfies Property~\eqref{it:od}.  By induction we get $y\leq_{3}c$, and thus by \cref{prop:alternating_covers} we conclude $x\lessdot_{3}y\leq_{3}c$.
\end{proof}

\begin{figure}
	\begin{tikzpicture}\small
		\def\x{1.15};
		\def\y{3};
		\def\s{.5};
		%%
		\draw(7.5*\x,1.25*\y) node[scale=\s](n1){$(1)$};
		\draw(1*\x,2*\y) node[scale=\s](n2){$(1\;6\;7)$};
		\draw(2*\x,2*\y) node[scale=\s](n3){$(2\;3\;6)$};
		\draw(3*\x,2*\y) node[scale=\s](n4){$(4\;5\;6)$};
		\draw(4*\x,2*\y) node[scale=\s](n5){$(1\;4\;7)$};
		\draw(5*\x,2*\y) node[scale=\s](n6){$(2\;3\;4)$};
		\draw(6*\x,2*\y) node[scale=\s](n7){$(2\;5\;6)$};
		\draw(7*\x,2*\y) node[scale=\s](n8){$(1\;2\;7)$};
		\draw(8*\x,2*\y) node[scale=\s](n9){$(3\;4\;7)$};
		\draw(9*\x,2*\y) node[scale=\s](n10){$(5\;6\;7)$};
		\draw(10*\x,2*\y) node[scale=\s](n11){$(1\;2\;5)$};
		\draw(11*\x,2*\y) node[scale=\s](n12){$(3\;4\;5)$};
		\draw(12*\x,2*\y) node[scale=\s](n13){$(3\;6\;7)$};
		\draw(13*\x,2*\y) node[scale=\s](n14){$(1\;2\;3)$};
		\draw(14*\x,2*\y) node[scale=\s](n15){$(1\;4\;5)$};
		\draw(1*\x,3*\y) node[scale=\s](n16){$(1\;6\;7)(3\;4\;5)$};
		\draw(2*\x,3*\y) node[scale=\s](n17){$(1\;2\;3\;6\;7)$};
		\draw(3*\x,3*\y) node[scale=\s](n18){$(1\;2\;3)(4\;5\;6)$};
		\draw(4*\x,3*\y) node[scale=\s](n19){$(1\;4\;5\;6\;7)$};
		\draw(5*\x,3*\y) node[scale=\s](n20){$(1\;6\;7)(2\;3\;4)$};
		\draw(6*\x,3*\y) node[scale=\s](n21){$(2\;3\;4\;5\;6)$};
		\draw(7*\x,3*\y) node[scale=\s](n22){$(1\;2\;7)(4\;5\;6)$};
		\draw(8*\x,3*\y) node[scale=\s](n23){$(1\;2\;3\;4\;7)$};
		\draw(9*\x,3*\y) node[scale=\s](n24){$(2\;3\;4)(5\;6\;7)$};
		\draw(10*\x,3*\y) node[scale=\s](n25){$(1\;2\;5\;6\;7)$};
		\draw(11*\x,3*\y) node[scale=\s](n26){$(1\;2\;7)(3\;4\;5)$};
		\draw(12*\x,3*\y) node[scale=\s](n27){$(3\;4\;5\;6\;7)$};
		\draw(13*\x,3*\y) node[scale=\s](n28){$(1\;2\;3)(5\;6\;7)$};
		\draw(14*\x,3*\y) node[scale=\s](n29){$(1\;2\;3\;4\;5)$};
		\draw(7.5*\x,3.75*\y) node[scale=\s](n30){$(1\;2\;3\;4\;5\;6\;7)$};
		%%
		\draw(n1) -- (n2);
		\draw(n1) -- (n3);
		\draw(n1) -- (n4);
		\draw(n1) -- (n5);
		\draw(n1) -- (n6);
		\draw(n1) -- (n7);
		\draw(n1) -- (n8);
		\draw(n1) -- (n9);
		\draw(n1) -- (n10);
		\draw(n1) -- (n11);
		\draw(n1) -- (n12);
		\draw(n1) -- (n13);
		\draw(n1) -- (n14);
		\draw(n1) -- (n15);
		\draw(n2) -- (n16);
		\draw(n2) -- (n17);
		\draw(n2) -- (n19);
		\draw(n2) -- (n20);
		\draw(n2) -- (n25);
		\draw(n3) -- (n17);
		\draw(n3) -- (n21);
		\draw(n4) -- (n18);
		\draw(n4) -- (n19);
		\draw(n4) -- (n21);
		\draw(n4) -- (n22);
		\draw(n4) -- (n27);
		\draw(n5) -- (n19);
		\draw(n5) -- (n23);
		\draw(n6) -- (n20);
		\draw(n6) -- (n21);
		\draw(n6) -- (n23);
		\draw(n6) -- (n24);
		\draw(n6) -- (n29);
		\draw(n7) -- (n21);
		\draw(n7) -- (n25);
		\draw(n8) -- (n17);
		\draw(n8) -- (n22);
		\draw(n8) -- (n23);
		\draw(n8) -- (n25);
		\draw(n8) -- (n26);
		\draw(n9) -- (n23);
		\draw(n9) -- (n27);
		\draw(n10) -- (n19);
		\draw(n10) -- (n24);
		\draw(n10) -- (n25);
		\draw(n10) -- (n27);
		\draw(n10) -- (n28);
		\draw(n11) -- (n25);
		\draw(n11) -- (n29);
		\draw(n12) -- (n16);
		\draw(n12) -- (n21);
		\draw(n12) -- (n26);
		\draw(n12) -- (n27);
		\draw(n12) -- (n29);
		\draw(n13) -- (n17);
		\draw(n13) -- (n27);
		\draw(n14) -- (n17);
		\draw(n14) -- (n18);
		\draw(n14) -- (n23);
		\draw(n14) -- (n28);
		\draw(n14) -- (n29);
		\draw(n15) -- (n19);
		\draw(n15) -- (n29);
		\draw(n16) -- (n30);
		\draw(n17) -- (n30);
		\draw(n18) -- (n30);
		\draw(n19) -- (n30);
		\draw(n20) -- (n30);
		\draw(n21) -- (n30);
		\draw(n22) -- (n30);
		\draw(n23) -- (n30);
		\draw(n24) -- (n30);
		\draw(n25) -- (n30);
		\draw(n26) -- (n30);
		\draw(n27) -- (n30);
		\draw(n28) -- (n30);
		\draw(n29) -- (n30);
	\end{tikzpicture}
	\caption{The poset $\penc_{7}=(\enc_{7},\leq_{3})$.}
	\label{fig:enc_7}
\end{figure}


\cref{fig:enc_7} shows the poset $\penc_{7}=(\enc_{7},\leq_{3})$. We remark that this is \emph{not} a lattice, contrary to the usual lattice of noncrossing partitions. An important property of $\enc_{N}$ is that it is closed under taking Kreweras complements.

\begin{proposition}\label{prop:enc_kreweras}
	Let $y\in\enc_{N}$ and $x\leq_{3}y$.  If $x\in\enc_{N}$, then $K_{y}(x)=x^{-1}y\in\enc_{N}$. 
\end{proposition}

We skip the proof, which consists of a simple verification of the cycle structure $x^{-1}$, based on the characterization of \cref{thm:enc_interval}. We are now in the position to prove \cref{thm:induced_subposet}.

\begin{proof}[Proof of \cref{thm:induced_subposet}]
\cref{prop:odd_alternating,prop:enc_kreweras} imply that for all $x\in\enc_{N}$ we have $\ell_{3}(x)=\tfrac{\ell_{2}(x)}{2}$.  By definition, we conclude $x\leq_{3}y$ if and only if $x\leq_{2}y$ for all $x,y\in\enc_{N}$, which settles the claim for all intervals in $\penc_{N}$.  Moreover, any $y\in\AAo_{N}$ is $\SS_{N}$-conjugate to some $x\in\enc_{N}$.  The conjugation-invariance of $\ell_{3}$ together with the first part of this proof settles the claim.
\end{proof}

%%%%%%%%%%%%%%%%	
\section{Enumerative Results}
	\label{sec:enumeration}
%%%%%%%%%%%%%%%%

We further investigate the poset $\penc_{2n+1}$ by presenting enumerative results, \cref{thm:enc_multichains,thm:enc_zeta}, which are counterparts of similar ones for $\pnc_{n}$, see~\cite{edelman80chain} for instance.\smallskip

 Recall that an \defn{$m$-multichain} in a graded poset $(P,\leq)$ of rank $n$ is a tuple $(x_{1},x_{2},\ldots,x_{m})$ with $x_{1}\leq x_{2}\leq\cdots\leq x_{m}$, and that the \defn{rank-jump vector} of such an $m$-multichain is the $(m+1)$-tuple $\bigl(\rk(x_{1}),\rk(x_{2}-x_{1}),\ldots,\rk(x_{m})-\rk(x_{m-1}),n-\rk(x_{m})\bigr)$.  We start  with the proof of \cref{thm:enc_multichains}.

\begin{proof}[Proof of \cref{thm:enc_multichains}]
	An $(m-1)$-multichain with rank-jump vector $(r_{1},r_{2},\ldots,r_{m})$ in the poset $\penc_{2n+1}$ corresponds bijectively to a factorization $(1\;2\;\cdots\;2n\!+\!1)=y_1y_2\cdots y_{m}$ that is reduced for $\ell_{3}$, and where $y_i\in\AAo_{2r_i+1}$ for $i\in\{1,2,\ldots,m\}$. Since $\penc_{2n+1}$ is an induced subposet of $\pnc_{2n+1}$ (\cref{thm:induced_subposet}), one can assume equivalently that the factorization is reduced for $\ell_{2}$. Therefore we are in the setting of \cite[Lemma 4~and~Theorem 5]{krattenthaler10decomposition} which gives us the result.
\end{proof}

As a special case, by  taking $m=2$ and $(r_1,r_2)=(k,n-k)$ we find that the number of elements of rank $k$ in $\penc_{2n+1}$  is given by
\begin{displaymath}
	\frac{2n+1}{(2n-2k+1)(2k+1)}\binom{2n-k}{k}\binom{n+k}{n-k}.
\end{displaymath}

Also, there are $(2n+1)^{n-1}$ maximal chains in this poset; by definition this is equivalently the cardinality of $\red_{3}(c)$ for $c=(1\;2\;\cdots\;2n\!+\!1)$.\medskip

 Recall further that the \defn{zeta polynomial} $Z(\PP,m)$ of a poset $\PP$ counts the number of $(m-1)$-multichains in the poset when $m$ is a positive integer.

\begin{theorem}\label{thm:enc_zeta}
	For $n\geq 1$, the zeta polynomial of $\penc_{2n+1}$ is
	\begin{displaymath}
		Z(\penc_{2n+1},m) = \frac{m}{(2m-1)n+m}\binom{(2m-1)n+m}{n}.
	\end{displaymath}
\end{theorem}
\begin{proof} 
	By definition, one needs to sum the formula of \cref{thm:enc_multichains} over all rank jump vectors of size $m$ that sum up to $n$. To do this, one needs to use a multivariate generalization of the Rothe-Hagen identity~\cite{gould56some}.
\end{proof}

As a corollary, we can conclude the cardinality, the number of intervals and the M{\"o}bius number of $\penc_{2n+1}$: these correspond indeed to the evaluation of the zeta polynomials at $m=2$, $m=3$, and $m=-1$, respectively. 

\begin{corollary}
\label{cor:enum}
	For $n\geq 1$, the poset $\penc_{2n+1}$ has $\frac{1}{n+1}\binom{3n+1}{n}$ elements, $ \frac{3}{5n+3}\binom{5n+3}{n}$ intervals, and its M{\"o}bius number is $ \frac{(-1)^{n}}{4n+1}\binom{4n+1}{n}$.
\end{corollary}

We end this section with two remarks, which concern respectively bijections and the connection to combinatorial maps.

\begin{remark} In the full version of this abstract we provide bijective proofs for some of the above results.  We mention two of them: first,  the characterization of \cref{thm:enc_interval} enables us to restrict the classical correspondence~\cite{goulden92combinatorial} between noncrossing partitions and planar bicolored trees to our setting.  We obtain a bijection between $\enc_{2n+1}$  and marked bicolored plane trees where all vertices have odd degree and a total of $2n+1$ edges: these are in bijection with plane ternary trees thus proving the first formula of \cref{cor:enum}.  Secondly, we can also generalize Biane's bijective approach \cite{biane02parking} between maximal chains in $\pnc_{n+1}$ and parking functions of length $n$ to our setting. This gives us a bijection between maximal chains in $\penc_{2n+1}$ and \defn{$2$-parking functions} of length $n$.

 It would be interesting to generalize Edelman's bijections for $\nc_{n}$~\cite{edelman80chain} (a mere restriction of his construction does not seem sufficient to obtain closed formulas). This would give full bijective proofs for \cref{thm:enc_multichains,thm:enc_zeta}. 
\end{remark}

\begin{remark}
These enumerative results are related to combinatorial maps in the following way: there is a nice dictionary between maps and certain factorizations of permutations $\sigma=x_1x_2\ldots x_k\in\SS_{n}$, see~\cite{bousquet00constellations}. In this context, only \defn{transitive} factorizations are considered, that is, the subgroup generated by the factors $x_i$ acts transitively on $\{1,2,\ldots,n\}$. Since $\ell_{2}$ is a length function, one has always $\ell_{2}(\sigma)\leq \sum_i\ell_{2}(x_i)$, and a \emph{minimal transitive factorization} is a transitive factorization where equality holds. Now factorizations of a long cycle are always transitive since such a cycle acts transitively, which explains why the results of this section can be interpreted in terms of maps. 

Assume now that the factors $x_i$ are $3$-cycles, and let $x\in \AA_{n}$. A simple computation shows that $\red_{3}(x)$ consists of minimal transitive factorizations if and only either (i) $n$ is odd and $x$ is a long, odd cycle or (ii) $n$ is even and $x$ is the product of two even cycles. We just dealt with (i), while the combinatorics of (ii) are a key element of the Hurwitz action in the next section.
\end{remark}

%%%%%%%%%%%%%%%%
\section{Hurwitz Orbits}
	\label{sec:hurwitz}
%%%%%%%%%%%%%%%%

This section is devoted to the proof of \cref{thm:hurwitz_transitivity}. To illustrate it, the five elements of $\red_{3}\bigl((1\;2\;3\;4\;5)\bigr)$ form a single Hurwitz orbit: \begin{displaymath}\begin{aligned}
	& (1\;2\;3)(3\;4\;5) && (3\;4\;5)(1\;2\;5) && (1\;2\;5)(2\;3\;4) && (2\;3\;4)(1\;4\;5) && (1\;4\;5)(1\;2\;3),
\end{aligned}\end{displaymath}
whereas $\red_{3}\bigl((1\;2)(3\;4)\bigr)$ contains eight words grouped in two Hurwitz orbits:
\begin{displaymath}\begin{aligned}
	& (1\;2\;3)(2\;3\;4), && (2\;3\;4)(2\;1\;4), && (2\;1\;4)(1\;4\;3), && (1\;4\;3)(1\;2\;3),\\
	& (1\;2\;4)(2\;4\;3), && (2\;4\;3)(2\;1\;3), && (2\;1\;3)(1\;3\;4), && (1\;3\;4)(1\;2\;4).
\end{aligned}\end{displaymath}

This differs from the case of $(\SS_{n},\leq_{2})$, since the Hurwitz action is always transitive on $\red_2{(x)}$, cf. \cite{bessis03dual}. We will prove the following precise result, of which \cref{thm:hurwitz_transitivity} is a direct corollary.

\begin{theorem}\label{thm:hurwitz_orbits}
	Let $x\in\AA_{N}$, and denote by $2k$ the number of its even cycles.  Then the Hurwitz action on $\red_{3}(x)$ has $(2k)!/k!=(k+1)(k+2)\cdots(2k)$ orbits.
\end{theorem}

As a first step, note that \cref{prop:interval_decomposition} gives us a global structure for $\red_{3}(x)$: keeping the notation, it says that elements of $\red_{3}(x)$ are exactly the ``shuffling'' of elements of the union of all $\red_{3}(\zeta_i)$ with $\red_{3}(\xi)$. Notice also that if, in a given word, two adjacent letters in positions $i$ and $i+1$ commute, then the Hurwitz operator $\sigma_i$ performs this commutation.  

This implies that in order to prove \cref{thm:hurwitz_orbits} it suffices to show that its statement holds (i) for $x$ an odd cycle, and (ii) for $x$ having only even cycles. Since our results are invariant under conjugation, Case (i) is dealt with in the following proposition.  

\begin{proposition}\label{prop:hurwitz_odd}
	Let $c=(1\;2\;\cdots\;2n\!+\!1)\in \AA_{N}$. The Hurwitz action is transitive on $\red_{3}(c)$.
\end{proposition}

\begin{proof}[Sketch of the proof]
	This is done by induction on length, following the lines of the proof of \cite[Proposition~1.6.1]{bessis03dual}. We start with the  word $\xx=(1\;2\;3)(3\;4\;5)\cdots(2n\!-\!1\;2n\;2n\!+\!1)$ in $\red_{3}(c)$. By picking well-chosen elements in the braid group, one shows that for any 3-cycle $a\leq_3 c$, there exists a word $\yy a$ which is Hurwitz-equivalent to $\xx$. Now $\yy$ represents an element $y$ covered by $c$, and so $y$ has only odd cycles. By induction, the Hurwitz orbit of $\yy$ is the whole of $\red_{3}(y)$, which proves the proposition.
\end{proof}

Now we deal with Case (ii), so let $x=\xi_{1}\xi_{2}\cdots\xi_{2k}\in\AA_{N}$ have only even cycles, which form a set $E(x)=\{\xi_{1},\xi_{2},\ldots,\xi_{2k}\}$. Given $\xx\in\red_{3}(x)$, define a \defn{partition $M_{\xx}$ of $E(x)$} as follows: $\xi_{i},\xi_{j}$ are in the same block of $M_{\xx}$ if there exists a $3$-cycle $(a_1\;a_2\;a_3)$ in the word $\xx$ which commutes neither with $\xi_i$ nor with $\xi_j$; then extend by transitivity. 

Recall that a (perfect) matching is a partition where all blocks have size $2$. Then the following proposition is a consequence of the cover relations described in \cref{prop:alternating_covers}.

\begin{proposition}\label{prop:even_cycles_matching}
	$M_{\xx}$ is a matching which is invariant under the Hurwitz action on $\red_{3}(x)$.
\end{proposition}

This result stresses the role of the case $|E(x)|=2$, and so we consider the case $x=(a_{1}\;a_{2}\;\ldots\;a_{2p})(b_{1}\;b_{2}\;\ldots\;b_{2q})\in\AA_{N}$. The 3-cycles $a\leq_{3}x$ can be divided into two families: On the one hand, \defn{pure generators} have the form $(a_{i}\;a_{j}\;a_{k})$ or $(b_{i}\;b_{j}\;b_{k})$ where $i<j<k$  (one can then show that exactly one element among $j-i$, $k-j$, and $i-k$ is even).  On the other hand, \defn{mixed generators}  have the form $(a_{i}\;a_{j}\;b_{k})$ or $(a_{i}\;b_{j}\;b_{k})$  (here $j-i$ must be odd in $(a_{i}\;a_{j}\;b_{k})$ and $k-j$ must be odd in $(a_{i}\;b_{j}\;b_{k})$).  The \defn{parity} of a mixed generator of $\xx$ is by definition the parity of $k-i$.  

\begin{lemma}\label{lem:hurwitz_even}
	Let $\xx\in\red_{3}(x)$.  Then $\xx$ contains at least two mixed generators, and all of its mixed generators have the same parity. 
\end{lemma}

We can therefore unambiguously say that $\xx$ is \defn{even} (respectively \defn{odd}) if it contains an even (respectively odd) mixed generator. Note that for the two orbits of $\red_{3}\bigl((1\;2)(3\;4)\bigr)$ determined at the beginning of the section, the first one consists of odd words.

\begin{proof}[Sketch of the proof of \cref{lem:hurwitz_even}]
	The fact that  $\xx$ contains at least two mixed generators is a consequence of \cref{prop:alternating_covers} once again, since the cycle factorization cannot be achieved with zero or one mixed generator. Now pick two mixed generators in $\xx$: we can assume that they occur at the last two positions of $\xx$ by using the Hurwitz action to place them there. A tedious case analysis based once again on \cref{prop:alternating_covers} shows that these generators have the same parity. 
\end{proof}

\begin{proof}[Proof of \cref{thm:hurwitz_orbits} (sketch)]
	In view of \cref{prop:hurwitz_odd} and the discussion preceding it,  it remains to deal with the case when $x$ has only even cycles.

	Assume first $k=1$ and write $x=(a_{1}\;a_{2}\;\cdots\;a_{2p})(b_{1}\;b_{2}\;\cdots\;b_{2q})$.  Let $\xx\in\red_{3}(x)$, and suppose without loss of generality that $\xx$ contains an even mixed generator.  Remark that by definition the action of $\sigma_{i}$ modifies at most one letter. The potential new letter cannot be an odd mixed generator because that would contradict \cref{lem:hurwitz_even}.  It follows immediately that, in a Hurwitz orbit of $\red_{3}(x)$, all words have the same parity.  Since it is easy to check that words of both parities occur in $\red_{3}(x)$, the Hurwitz action on $\red_{3}(x)$ has at least two orbits. 

	We need to prove that there are exactly two orbits; equivalently, we must show that words of a given parity form a single orbit. It is enough to show \emph{Hurwitz-transitivity for even reduced words for $x$}. Indeed, if we rewrite the second cycle as $(b_{2}\;b_{3}\;\cdots\;b_{2q}\;b_{1})$, then it is quickly checked that the even words relative to one writing are in $1$-to-$1$ correspondence with the odd words relative to the other writing, by changing $b_{i}$ to $b_{i+1}$ everywhere. 
 
	The proof of this transitivity is a bit more technical than the proof of \cref{prop:hurwitz_odd}, but the main steps are similar: First, we fix a particular even word $\xx$ in $\red_{3}(x)$, and we show that any $3$-cycle $a\leq_{3}x$ which is pure or (mixed) even, occurs as the last letter of an element in the orbit of $\xx$.  Then we must study the Hurwitz action on $\red_{3}(x')$ for all $x'\lessdot_{3}x$ such that $x=x'a$ with $a$ as above.  In view of \cref{prop:alternating_covers}, there are two possibilities for $x'$:  either $x'$ does not contain even cycles, in which case the transitivity follows from \cref{prop:hurwitz_odd}, or $x'$ contains two even cycles, in which case we get transitivity on even words by induction on $\ell_{3}(x)$ (here one must take care of writing the new even cycles with increasing indices for $a_i$'s and $b_j$'s). \smallskip

	Now we return to the case of general $k$. We showed that for any matching $M$ among the even cycles of $x$, and a choice of ``parity'' for each one of the $k$ pairs of $M$, we obtain a Hurwitz-invariant subset $S$ of $\red_{3}(x)$.  It follows that there are at least $(2k-1)!!2^{k}=(2k)!/k!$ Hurwitz orbits.  To finish the proof, we must show that the Hurwitz action is transitive on any such $S$.  Since generators with support in distinct pairs of $M$ commute, and the Hurwitz action performs this commutation when the generators are adjacent as mentioned above, it is equivalent to show that for any pair $\{\xi_{i},\xi_{j}\}$ in $M_{x}$ the Hurwitz action on $\red_3(\xi_i\xi_j)$ has two orbits. We are thus in the known case of two even cycles, and the proof is complete.
\end{proof}

%%%%%%%%%%%%%%%%	
\section{Extensions}
	\label{sec:extensions}
%%%%%%%%%%%%%%%%	
 
\subsection{Generation by  $k$-Cycles}
In this abstract we investigated the order on the alternating group generated by all $3$-cycles, and we stressed the many nice parallels to the case of the symmetric group generated by all $2$-cycles.  A natural question is  to consider the order $\leq_{k}$ on the subgroup of the symmetric group generated by all $k$-cycles (this subgroup is $\SS_{n}$ when $k$ is even, and $\AA_{n}$ when $k$  is odd.)  

It turns out that determining $\ell_{k}$ (and a fortiori $\leq_{k}$) seems already like  a hard problem in general.  In \cite{herzog76representation}, a complicated formula for $\ell_{4}$ is determined, but only bounds are given for $\ell_{k}$ for larger $k$. 

Things behave better when restricting to permutations that have only cycles of length $\equiv 1\pmod{k-1}$. The values of  $\ell_k$ and $\leq_{k}$ on these elements can be determined, and the results from \cref{sec:embedding,sec:enumeration} for $\AAo_{2n+1}$ generalize nicely.

\subsection{$m$-Divisible Even Noncrossing Partitions}
In the spirit of \cite{edelman80chain} and \cite{armstrong09generalized}, a possible generalization of $\penc_{2n+1}$ is to consider the poset $\penc_{2n+1}^{(m)}$ of $m$-multichains of $\penc_{2n+1}$.  Computer experiments suggest the following result for the zeta polynomial of this poset.

\begin{conjecture}
	For $n,m\geq 1$ the zeta polynomial of $\penc_{2n+1}^{(m)}$ is 
	\begin{displaymath}
		Z\bigl(\penc_{2n+1}^{(m)},q\bigr) = \frac{m(q-1)+1}{(2m(q-1)+1)n+m(q-1)+1}\binom{(2m(q-1)+1)n+m(q-1)+1}{n}.
	\end{displaymath}
\end{conjecture}

\subsection{Alternating Subgroups of Coxeter Groups}
There is a natural way to extend the construction of the poset $(\AA_{N},\leq_{3})$ to any irreducible Coxeter system $(W,S)$ with Coxeter matrix $(m_{st})$.  The \emph{alternating subgroup} $\AA(W)$ of $W$ is by definition the kernel of the sign character of $W$. If ${T}=\{w^{-1}sw\mid w\in W, s\in S\} $ is the set of \defn{reflections}, then one has equivalently $\AA(W)=\{w\in W\mid \ell_{T}(w)\equiv 0\pmod{2}\}$.  

We noticed that $\AA(W)$ is generated by the set 
\begin{displaymath}
	A(W)= \bigl\{w^{-1}stw\mid w\in W, m_{st}\geq 3\bigr\}.
\end{displaymath}
Note that we exclude pairs of commuting generators $s,t$: in the case of the symmetric group, this means that $A$ does not contain double transpositions,  but only $3$-cycles as desired.  The set $A=A(W)$ can be interpreted as the conjugation-closure of the \emph{edges} of the Coxeter diagram of $W$.  We are then interested in extending the results of this abstract to the generated group $\bigl(\AA,A\bigr)$ and its associated length $\ell_{A}$ and order $\leq_{A}$. \smallskip

We are only in  the preliminary stages of this investigation, but we performed some computer explorations in type $B_N$. Thus for $N\geq 2$, we have $\ell_{A(B_N)}(x)=\frac{N-\ocyc(x)}{2}$ for a natural statistic of odd cycles for signed permutations.

Recall that a \emph{Coxeter element} $c$ of $W$ is a product of any permutation of the Coxeter generators of $W$, and $\ell_T(W)$ equals the rank of $W$.  As a consequence, Coxeter elements belong to $\AA(W)$ if and only if $W$ has even rank.  In $\SS_{N}$, the Coxeter elements are precisely the $N$-cycles, and it is therefore an intriguing question to ask if the poset 
\begin{displaymath}
	\enc_{W}(c) = \{x\in\AA(W)\mid x\leq_{A}c\}
\end{displaymath}
plays a role analogous to $\enc_{2n+1}$ for $\AA_{2n+1}$.  In this direction, we conjecture the following zeta polynomial for type $B_{2n}$.

\begin{conjecture}\label{conj:type_b}
	For $n\geq 1$, the zeta polynomial of $\penc_{B_{2n}}$ is 
	\begin{displaymath}
		Z\bigl(\penc_{B_{2n}},q\bigr) = \frac{q}{2q-1}\binom{(2q-1)n}{n}.
	\end{displaymath}
\end{conjecture}


\printbibliography



\end{document}
